1. Technical Field
This invention relates to computerized transaction processing systems. More particularly, it relates to a method for reducing locking by transactions which are executing concurrently.
2. Description of the Prior Art
Transaction Processing
A transaction comprises a sequence of operations that changes recoverable data such as a database from one consistent state into another. A transaction processing system guarantees that if a transaction executes some updates against recoverable data, and if a failure occurs before the transaction reaches its normal termination or an interim point of consistency, then those updates will be undone. When a new point of consistency has been reached and all updates made by the transaction must be made permanent, the transaction is committed.
To fulfill this transaction recovery guarantee, the system must be able to remember across system outages both transactions in progress and their update actions, so that their effect on recoverable data can be properly reflected when the system is restarted. The system maintains a log of each transaction's progress and changes to data in order to fulfill the transaction recovery guarantee. The log data, known as log records, can be examined to ensure that either the transaction's committed actions are reflected in the data base or were undone. When the log records include actual data, they can also be used to reconstruct data which has been damaged or lost, such as by the failure of a storage device. The log can be thought of as an ever growing sequential file.
The log is permanently stored on stable storage such as a disk file (often called a "disk drive"), which remains intact and available across system failures. Log records are first written to temporary, volatile log file buffers in the computer's memory, and then transferred to stable storage at certain times (e.g., when a transaction is committed).
Locking
Both stable storage (e.g., disk storage) and virtual storage (e.g., computer memory) are divided into pages. Each page typically holds the equivalent of several typewritten pages. The page may be subdivided into records, such as the names and addresses of individuals. When a transaction needs to access certain data, the page containing that data is copied from stable storage into a buffer of the same size in virtual storage. If the data is updated by the transaction the updated page is transferred back to stable storage at a later time.
Locking is used to control simultaneously executing (i.e. concurrent) transactions' access to shared data, and in particular is used to prevent concurrent transactions from inconsistently modifying the same data. Appropriate use of locking can guarantee a transaction that the data that it reads is in a consistent state and that the data does not contain uncommitted updates of other transactions.
Systems which use page-level locking cannot lock less than a whole page, even if the transaction obtaining the lock only needs to access one of the records on the page. Locking at a finer granularity, such as record-level locking can reduce contention between concurrent transactions, but imposes greater processing overhead.
Locking is time consuming ("expensive" in technical terms), and therefore slows the processing of transactions. Storage for individual locks' information must be acquired, formatted and released, and machine instructions must be executed to acquire and release locks. In one transaction processing system, acquiring a lock and releasing it requires about 800 instructions even when there are no conflicts with other locks or requests.
Lock managers typically process lock requests in a first-in-first-out (FIFO) basis in order to fairly allocate locks among competing transactions. As a result, sometimes a transaction must wait for a lock even though its requested lock can be granted, because its request is not compatible with an intervening request from another transaction.
Record-level and similar fine-granularity locking can be helpful in increasing concurrency by reducing contention among transactions. It is well known in the art that locking granularity affects system throughput. Typically, finer-granularity of locking leads to higher throughput. The drawback of fine-granularity locking is that for those transactions that access large number of records, the number of locks that need to be acquired may increase dramatically.
In many cases the sole purpose of locking is to ensure that a given piece of data that is about to be read is in the committed state, rather than to delay future updates. Ad hoc queries that examine large volumes of data and that generally do not perform any updates of the examined data are examples of locking to ensure that data is committed. In these situations, known prior art techniques either do not apply or are too time consuming (in terms of machine instructions).
There is a significant body of prior art relating to locking reduction. Ng, U.S. Pat. No. 4,627,019, "Database Management System for Controlling Concurrent Access to a Database", and Gallant, U.S. Pat. No. 4,648,036, "Method for Controlling Query and Update Processing in a Database System", disclose methods in which multiple versions of the data are maintained to avoid locking by read-only transactions. Ng discloses storing an array of access blocks, each block defining the database location of a version of the data, with only one version being current. However versioning does not avoid locking for transactions which need completely current data. Versioning only helps transactions which perform no updates and which do not mind reading outdated data. Further, versioning requires extra storage to maintain the multiple versions of updated data objects. Goldstein et al., U.S. Pat. No. 4,698,752, avoids relocking records by maintaining a transaction list identifying locked records which were previously locked by the same. transaction.
Instead of avoiding locking, Kung and Robinson, "On Optimistic Methods for Concurrency Control", ACM Transactions on Database Systems, vol. 6, no. 2, pp. 213-226 (June 1981), propose an approach called "optimistic locking" for reducing the cost of locking.
There is a need for a transaction processing system which does not require transactions to obtain unnecessary locks. There is also a need for a method for more efficiently determining that a piece of data is in the committed state. Finally, there is a need to support fine-granularity locking in a way that is not too time consuming for transactions reading large quantities of data.